package demo;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //统计好数字的数目
    private static final int MOD = 1000000007;

    private static long modPow(long base, long exp) {
        long prod;
        for (prod = 1; exp != 0; base = base * base % MOD, exp >>>= 1)
            if ((exp & 1) != 0)
                prod = prod * base % MOD;
        return prod;
    } // modPow(long, long)

    public int countGoodNumbers(long n) {
        return (int) (modPow(4, n >>> 1) * modPow(5, n + 1 >>> 1) % MOD);
    } // countGoodNumbers(long)
}
